package demo5;

import java.util.*;

class Edge {
    int vertex; // 目标顶点
    int weight; // 边权重

    Edge(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }
}

public class SingleSourceShortestPath {
    private int[][] c; // 邻接矩阵
    private int[] dist; // 最短路径长度
    private int[] pre; // 前驱数组
    private int n; // 顶点数

    public SingleSourceShortestPath(int[][] c, int n) {
        this.c = c;
        this.n = n;
        this.dist = new int[n];
        this.pre = new int[n];
    }

    public void shortestPath(int source) {
        // 初始化
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始距离设为无穷大
        Arrays.fill(pre, -1); // 初始前驱设为-1
        dist[source] = 0; // 源点到自身的距离为0

        // 优先队列，存储<顶点, 当前距离>，按距离升序排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{source, 0}); // 加入源点

        // 访问标记数组
        boolean[] visited = new boolean[n];

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0]; // 当前顶点
            int currDist = curr[1]; // 当前距离

            // 如果已访问，跳过
            if (visited[u]) continue;

            visited[u] = true; // 标记为已访问

            // 遍历邻接顶点
            for (int v = 0; v < n; v++) {
                // 检查是否有边且未访问
                if (c[u][v] != Integer.MAX_VALUE && !visited[v]) {
                    int newDist = dist[u] + c[u][v]; // 新路径长度
                    if (newDist < dist[v]) { // 如果找到更短路径
                        dist[v] = newDist; // 更新最短路径长度
                        pre[v] = u; // 更新前驱
                        pq.offer(new int[]{v, newDist}); // 加入优先队列
                    }
                }
            }
        }
    }

    // 打印最短路径
    public void printPath(int source) {
        System.out.println("从源点 " + source + " 到各顶点的最短路径：");
        for (int i = 0; i < n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("到顶点 " + i + " 无路径");
            } else {
                System.out.print("到顶点 " + i + " 的最短路径长度: " + dist[i] + ", 路径: ");
                printPathRecursive(i);
                System.out.println();
            }
        }
    }

    // 递归打印路径
    private void printPathRecursive(int v) {
        if (pre[v] == -1) {
            System.out.print(v);
            return;
        }
        printPathRecursive(pre[v]);
        System.out.print(" -> " + v);
    }

    public static void main(String[] args) {
        int n = 5; // 5个顶点
        int[][] c = {
            {0, 10, Integer.MAX_VALUE, 30, 100},
            {Integer.MAX_VALUE, 0, 50, Integer.MAX_VALUE, Integer.MAX_VALUE},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, Integer.MAX_VALUE, 10},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, 20, 0, 60},
            {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };

        SingleSourceShortestPath ssp = new SingleSourceShortestPath(c, n);
        int source = 0; // 源点为0
        ssp.shortestPath(source);
        ssp.printPath(source);
    }
}